package demo.suanfa;

import java.util.Arrays;

public class _动态规划 {
    public static void main(String[] args) {
//        _走格子();
//        _走格子带障碍物();
//        _最小路径和问题();
        _分硬币();
    }

    private static void _分硬币() {
        int[] coins = {1, 3, 4};
        int mount = 6;
        // 求最少硬币找零
        // 金额i的最优解dp[i]=dp[i-coin]+1
        int[] dp = new int[mount + 1];
        Arrays.fill(dp, mount + 1);
        dp[0] = 0;

        // choice[i]表示凑出金额i时选择的最后一枚硬币的面值
        int[] choice = new int[mount + 1];// ？？
        choice[0] = -1;
        for (int i = 1; i <= mount; i++) {
            for (int coin : coins) {
                if (i >= coin && dp[i - coin] + 1 < dp[i]) {
                    // dp[i]表示凑出金额i所需的最少硬币数
//                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                    dp[i] = dp[i - coin] + 1;
                    choice[i] = coin; // 记录选择这枚硬币
                }
            }
        }
        System.out.println(dp[mount] > mount ? -1 : dp[mount]);
    }

    /**
     * 最小路径和问题
     *
     * @param grid 带权值的网格
     * @return 最小路径和
     */
    private static void _最小路径和问题() {
        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];

        dp[0][0] = grid[0][0];

        //初始化第一列
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        //初始化第一行
        for (int i = 1; i < m; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        System.out.println();
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[j][i - 1]) + grid[i][j];
            }
        }
        System.out.println("最小路径和: " + dp[m - 1][n - 1]);
    }

    /**
     * 有障碍物的走格子问题
     *
     * @param obstacleGrid 网格，1表示障碍物，0表示空地
     * @return 路径总数
     */
    private static void _走格子带障碍物() {
        /**
         * 关键要点总结
         * 起点检查：起点有障碍物直接返回0
         * 终点检查：终点有障碍物直接返回0
         * 第一列逻辑：只能从上到下，遇到障碍物后面全部为0
         * 第一行逻辑：只能从左到右，遇到障碍物后面全部为0
         * 障碍物处理：有障碍物的格子路径数始终为0
         */
        int[][] arrs = {
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}
        };

        int m = arrs.length;
        int n = arrs[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = 1;// 起点只有1种方式(不动)
        // 初始化第一列
        for (int i = 1; i < m; i++) {
            if (arrs[i][0] == 1) {
                // 当前格子有障碍物，无法到达
                dp[i][0] = 0;
            } else {
                // 当前格子无障碍物，只能从上方格子下来
                dp[i][0] = dp[i - 1][0];
            }
        }

        // 初始化第一行
        for (int j = 1; j < n; j++) {
            if (arrs[0][j] == 1) {
                // 当前格子有障碍物，无法到达
                dp[0][j] = 0;
            } else {
                // 当前格子无障碍物，只能从左边格子过来
                dp[0][j] = dp[0][j - 1];
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (dp[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        System.out.println(dp[m - 1][n - 1]);
    }

    private static void _走格子() {
        /**
         * 在一个m×n的网格中，从左上角走到右下角，
         * 每次只能向右或向下移动，问有多少种不同的路径
         * 无障碍物
         */
        int m = 3, n = 3; // m行n列
        int[][] nums = new int[m][n];
        int[][] dp = new int[m][n];

        //初始化边界
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        // dp[i][j]=dp[i-1][j]+dp[i][j-1]
        System.out.println(dp[m - 1][n - 1]);
    }
}
